#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/12 9:42
# @USER    : Shengji He
# @File    : TrappingRainWater.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List

"""
- Array
- Two Pointers
- Dynamic Programming
- Stack
- Monotonic Stack
"""


class Stack:
    def __init__(self):
        self.__list = []

    def push(self, value):
        self.__list.append(value)

    def is_empty(self):
        return not bool(self.__list)

    def pop(self):
        if self.is_empty():
            raise LookupError('Stack is empty')
        else:
            self.__list.pop()

    def top(self):
        if self.is_empty():
            raise LookupError('Stack is empty')
        else:
            return self.__list[-1]


class Solution:
    """
    [42. Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/description/?envType=problem-list-v2&envId=dynamic-programming)
    Given n non-negative integers representing an elevation map where the width of each bar is 1,
    compute how much water it is able to trap after raining.
    Example:
        Input: [0,1,0,2,1,0,1,3,2,1,2,1]
        Output: 6
        Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

    Example 2:

        Input: height = [4,2,0,3,2,5]
        Output: 9


    Constraints:
        - n == height.length
        - 1 <= n <= 2 * 10^4
        - 0 <= height[i] <= 10^5
    """

    def trap(self, height: List[int]) -> int:
        """

        :param height: List[int]
        :return: int
        """
        st = Stack()
        ans = 0
        current = 0
        while current < len(height):
            while not st.is_empty() and height[current] > height[st.top()]:
                top = st.top()
                st.pop()
                if st.is_empty():
                    break
                distance = current - st.top() - 1
                bounded_height = min(height[current], height[st.top()]) - height[top]
                ans += distance * bounded_height
            st.push(current)
            current += 1
        return ans


if __name__ == '__main__':
    S = Solution()
    # height = [0,1,0,2,1,0,1,3,2,1,2,1]
    height = [0, 7, 1, 4, 6]
    # height = [4,2,3]
    print(S.trap(height))
    print('done')
